home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / utils / unix / unzip-5.12 / inflate.c < prev    next >
Text File  |  1994-08-22  |  38KB  |  1,078 lines
  1. /* inflate.c -- put in the public domain by Mark Adler
  2.    version c14o, 23 August 1994 */
  3.  
  4.  
  5. /* You can do whatever you like with this source file, though I would
  6.    prefer that if you modify it and redistribute it that you include
  7.    comments to that effect with your name and the date.  Thank you.
  8.  
  9.    History:
  10.    vers    date          who           what
  11.    ----  ---------  --------------  ------------------------------------
  12.     a    ~~ Feb 92  M. Adler        used full (large, one-step) lookup table
  13.     b1   21 Mar 92  M. Adler        first version with partial lookup tables
  14.     b2   21 Mar 92  M. Adler        fixed bug in fixed-code blocks
  15.     b3   22 Mar 92  M. Adler        sped up match copies, cleaned up some
  16.     b4   25 Mar 92  M. Adler        added prototypes; removed window[] (now
  17.                                     is the responsibility of unzip.h--also
  18.                                     changed name to slide[]), so needs diffs
  19.                                     for unzip.c and unzip.h (this allows
  20.                                     compiling in the small model on MSDOS);
  21.                                     fixed cast of q in huft_build();
  22.     b5   26 Mar 92  M. Adler        got rid of unintended macro recursion.
  23.     b6   27 Mar 92  M. Adler        got rid of nextbyte() routine.  fixed
  24.                                     bug in inflate_fixed().
  25.     c1   30 Mar 92  M. Adler        removed lbits, dbits environment variables.
  26.                                     changed BMAX to 16 for explode.  Removed
  27.                                     OUTB usage, and replaced it with flush()--
  28.                                     this was a 20% speed improvement!  Added
  29.                                     an explode.c (to replace unimplod.c) that
  30.                                     uses the huft routines here.  Removed
  31.                                     register union.
  32.     c2    4 Apr 92  M. Adler        fixed bug for file sizes a multiple of 32k.
  33.     c3   10 Apr 92  M. Adler        reduced memory of code tables made by
  34.                                     huft_build significantly (factor of two to
  35.                                     three).
  36.     c4   15 Apr 92  M. Adler        added NOMEMCPY do kill use of memcpy().
  37.                                     worked around a Turbo C optimization bug.
  38.     c5   21 Apr 92  M. Adler        added the WSIZE #define to allow reducing
  39.                                     the 32K window size for specialized
  40.                                     applications.
  41.     c6   31 May 92  M. Adler        added some typecasts to eliminate warnings
  42.     c7   27 Jun 92  G. Roelofs      added some more typecasts (444:  MSC bug).
  43.     c8    5 Oct 92  J-l. Gailly     added ifdef'd code to deal with PKZIP bug.
  44.     c9    9 Oct 92  M. Adler        removed a memory error message (~line 416).
  45.     c10  17 Oct 92  G. Roelofs      changed ULONG/UWORD/byte to ulg/ush/uch,
  46.                                     removed old inflate, renamed inflate_entry
  47.                                     to inflate, added Mark's fix to a comment.
  48.    c10.5 14 Dec 92  M. Adler        fix up error messages for incomplete trees.
  49.     c11   2 Jan 93  M. Adler        fixed bug in detection of incomplete
  50.                                     tables, and removed assumption that EOB is
  51.                                     the longest code (bad assumption).
  52.     c12   3 Jan 93  M. Adler        make tables for fixed blocks only once.
  53.     c13   5 Jan 93  M. Adler        allow all zero length codes (pkzip 2.04c
  54.                                     outputs one zero length code for an empty
  55.                                     distance tree).
  56.     c14  12 Mar 93  M. Adler        made inflate.c standalone with the
  57.                                     introduction of inflate.h.
  58.    c14b  16 Jul 93  G. Roelofs      added (unsigned) typecast to w at 470.
  59.    c14c  19 Jul 93  J. Bush         changed v[N_MAX], l[288], ll[28x+3x] arrays
  60.                                     to static for Amiga.
  61.    c14d  13 Aug 93  J-l. Gailly     de-complicatified Mark's c[*p++]++ thing.
  62.    c14e   8 Oct 93  G. Roelofs      changed memset() to memzero().
  63.    c14f  22 Oct 93  G. Roelofs      renamed quietflg to qflag; made Trace()
  64.                                     conditional; added inflate_free().
  65.    c14g  28 Oct 93  G. Roelofs      changed l/(lx+1) macro to pointer (Cray bug)
  66.    c14h   7 Dec 93  C. Ghisler      huft_build() optimizations.
  67.    c14i   9 Jan 94  A. Verheijen    set fixed_t{d,l} to NULL after freeing;
  68.                     G. Roelofs      check NEXTBYTE macro for EOF.
  69.    c14j  23 Jan 94  G. Roelofs      removed Ghisler "optimizations"; ifdef'd
  70.                                     EOF check.
  71.    c14k  27 Feb 94  G. Roelofs      added some typecasts to avoid warnings.
  72.    c14l   9 Apr 94  G. Roelofs      fixed split comments on preprocessor lines
  73.                                     to avoid bug in Encore compiler.
  74.    c14m   7 Jul 94  P. Kienitz      modified to allow assembler version of
  75.                                     inflate_codes() (define ASM_INFLATECODES)
  76.    c14n  22 Jul 94  G. Roelofs      changed fprintf to FPRINTF for DLL versions
  77.    c14o  23 Aug 94  C. Spieler      added a newline to a debug statement;
  78.                     G. Roelofs      added another typecast to avoid MSC warning
  79.  */
  80.  
  81.  
  82. /*
  83.    Inflate deflated (PKZIP's method 8 compressed) data.  The compression
  84.    method searches for as much of the current string of bytes (up to a
  85.    length of 258) in the previous 32K bytes.  If it doesn't find any
  86.    matches (of at least length 3), it codes the next byte.  Otherwise, it
  87.    codes the length of the matched string and its distance backwards from
  88.    the current position.  There is a single Huffman code that codes both
  89.    single bytes (called "literals") and match lengths.  A second Huffman
  90.    code codes the distance information, which follows a length code.  Each
  91.    length or distance code actually represents a base value and a number
  92.    of "extra" (sometimes zero) bits to get to add to the base value.  At
  93.    the end of each deflated block is a special end-of-block (EOB) literal/
  94.    length code.  The decoding process is basically: get a literal/length
  95.    code; if EOB then done; if a literal, emit the decoded byte; if a
  96.    length then get the distance and emit the referred-to bytes from the
  97.    sliding window of previously emitted data.
  98.  
  99.    There are (currently) three kinds of inflate blocks: stored, fixed, and
  100.    dynamic.  The compressor outputs a chunk of data at a time and decides
  101.    which method to use on a chunk-by-chunk basis.  A chunk might typically
  102.    be 32K to 64K, uncompressed.  If the chunk is uncompressible, then the
  103.    "stored" method is used.  In this case, the bytes are simply stored as
  104.    is, eight bits per byte, with none of the above coding.  The bytes are
  105.    preceded by a count, since there is no longer an EOB code.
  106.  
  107.    If the data is compressible, then either the fixed or dynamic methods
  108.    are used.  In the dynamic method, the compressed data is preceded by
  109.    an encoding of the literal/length and distance Huffman codes that are
  110.    to be used to decode this block.  The representation is itself Huffman
  111.    coded, and so is preceded by a description of that code.  These code
  112.    descriptions take up a little space, and so for small blocks, there is
  113.    a predefined set of codes, called the fixed codes.  The fixed method is
  114.    used if the block ends up smaller that way (usually for quite small
  115.    chunks); otherwise the dynamic method is used.  In the latter case, the
  116.    codes are customized to the probabilities in the current block and so
  117.    can code it much better than the pre-determined fixed codes can.
  118.  
  119.    The Huffman codes themselves are decoded using a mutli-level table
  120.    lookup, in order to maximize the speed of decoding plus the speed of
  121.    building the decoding tables.  See the comments below that precede the
  122.    lbits and dbits tuning parameters.
  123.  */
  124.  
  125.  
  126. /*
  127.    Notes beyond the 1.93a appnote.txt:
  128.  
  129.    1. Distance pointers never point before the beginning of the output
  130.       stream.
  131.    2. Distance pointers can point back across blocks, up to 32k away.
  132.    3. There is an implied